1. Field of the Invention
The present invention relates to error correction codes, and in particular to the decoding of turbo-codes.
2. Discussion of the Related Art
Turbo-codes, recently introduced, are error correction codes. Error correction codes have a technical effect and solve a significant technical problem. Indeed, they enable restoring the value of erroneous bits, for example, after a storage or a transmission. It can even be said that, without error correction codes, any digital information storage or transmission would be illusory. Turbo-codes are very efficient error correction codes.
FIG. 1A illustrates the principle of a turbo-coder, also called a turbo-code coder. On an input IN, the data digitized in the form of a bit sequence reach a coder 1 (COD). Coder COD is a simple coder which calculates and assigns to the data an error correction code in the form of redundancy bits. Coder COD may be of any known type, for example, a coder of convolutional, BCH, extended BCH, Reed Solomon, LDPC (“Low Density Parity Check”) type, etc.
The output of coder COD is sent to an interleaver 2. Interleaver 2 operates on blocks and provides the data received from a block in a different order. Interleaver 2 drives the input of a coder 3 (COD′). Coder COD′ is a simple coder of same type as coder COD. The data provided by output OUT of coder COD′ are said to be coded by turbo-codes and they include, in addition to the bits received as an input, the redundancy bits provided by coders COD and COD′.
FIG. 1B illustrates the principle of a turbo-decoder, also called a turbo-code decoder. On an input IN′, the turbo-decoder receives data coming from the turbo-code coder, generally after storage or transmission. The data to be decoded are sent to a decoder 1′ (DEC). Decoder DEC implements a function inverse to that of coder COD and it ensures a first decoding of the data. The output of decoder DEC is sent to an interleaver 2′ which implements the same interleaving operation as interleaver 2. The output of interleaver 2′ is sent to a decoder L(DEC′). Decoder DEC′ implements a function inverse to that of coder COD′. The output of decoder DEC′ is fed back into input IN′ via a deinterleaver 4. Deinterleaver 4 implements a deinterleaving function inverse to the function implemented by interleaver 2′.
The processing performed by elements DEC, 2′, DEC′, and 4 on an input data block forms an iteration.
Turbo-decoders perform several iterations based on the same input data, the number of corrected errors being all the greater as the number of iterations is great. The number of performed iterations depends on the desired BER (“Bit Error Rate”). A first half iteration is performed by decoder DEC and interleaver 2′ and a second half-iteration is performed by elements DEC′ and 4. In a second iteration, elements DEC, 2′, DEC′, and 4 carry the data coming from 4 in the first iteration, possibly after weighting and together with the input data of the original block.
In the last iteration, the data are sampled from an output OUT′, here the output of decoder DEC′.
When coders COD and COD′ are coders of convolutional type, the architectures of the turbo-coder and turbo-decoder follow closely enough the simplified diagrams of FIGS. 1A and 1B.
In the case where the data are coded, for example, by codings of BCH, extended BCH, Reed Solomon type, the turbo-coder and turbo-decoder architectures somewhat deviate from the simplified diagram.
FIG. 2A illustrates a block of data intended to be coded by means of such codes. The data block appears in the form of a rectangular table 6, including t2 lines and t1 columns. Data Di to be coded, in the form of bits, arrive one after the other and are arranged in table 6 in a known order. In FIG. 2A, t1=6 and t2=5. Data D0 to D5 fill the first line of the table, data D6 to D11 fill the second line of the table, and data D24 to D29 fill the last line of the table. Table 6 has the shape of a matrix and may be stored in a RAM.
FIG. 2B shows a rectangular table 10 illustrating the turbo-coding of data Di of block 6. Table 10 includes n2 lines and n1 columns, with n1>t1 and n2>t2. Table 10 is formed of three blocks. Block 6 of data Di is present at the top left. A block 7 including t2 lines and (n1−t1) columns is present to the right of block 6. Block 7 encloses codes Ci, in the form of bits, resulting from the application of coder COD. A block 8 including (n2−t2) lines and n1 columns is present under blocks 6 and 7. Block 8 encloses codes C′i, in the form of bits, resulting from the application of coder COD′. In FIG. 2B, n1=9 and n2=7.
Codes Ci are obtained by coding data Di line by line by means of coder COD. Thus, the coding of first line D0 to D5 of block 6 provides three codes C0, C1, and C2 which form the first line of block 7. The second line of block 7 encloses codes C3 to C5, resulting from the coding of data D6 to D11 and the last line of block 7 encloses codes C12, C13, and C14, corresponding to the coding of data D24 to D29.
When the line coding is over, the columns of blocks 6 and 7 are coded by means of code COD′. The first column of block 6, corresponding to data D0, D6, D12, D18, and D24, is coded by means of code COD′ and provides two codes C′0 and C′1, forming the first column of block 8. The same occurs for the next columns of block 6. The last line of block 6, corresponding to data D5, D11, D17, D23, and D29, provides codes C′10 and C′11 forming the sixth column of block 8.
The next columns of block 8 contain codes C′i resulting from the coding of bits Ci by coder COD′. Thus, the coding of the first column of block 7, corresponding to codes C0, C3, C6, C9, and C12, provides codes C′12 and C′13 forming the seventh column of block 8. The last column of block 7, containing codes C2, C5, C8, C11, and C14 provides, after coding by coder COD′, codes C′16 and C′17 forming the last column of block 8.
In the case of FIGS. 2A and 2B, the interleaving is performed by the successive coding of the data in lines and in columns, and a specific interleaving circuit is not useful.
The n1·n2 bits of block 10 are sent by any means to a turbo-decoder. The decoding is performed line by line, then column by column, one iteration being performed after a complete decoding of block 10. Several iterations are performed, to obtain a desired error rate.
A general problem of turbo-decoding is its slowness. Indeed, several iterations are required to obtain the desired error rate. These iterations implement complicated algorithms and the processing steps are relatively long. Further, in transmission, the data must be processed in real time by the turbo-decoder, and with a minimum latency. Beyond a given flow rate, the circuit which has performed the first iteration on a data block may not perform the next iterations, since the incoming data run against the data being processed.
A prior art solution to this problem is to arrange several turbo-decoders in series, each turbo-decoder performing an iteration. This results in turbo-decoding circuits of small compactness.